/*
 * This project provides a number of implementations for indexing and evaluating
 * <i>Continuous Top-k Queries over Text Streams</i>
 * and has been developped as part of the work described in the article:
 * 
 * Vouzoukidou, N., Amann, B., & Christophides, V. (2012, October). 
 * Processing continuous text queries featuring non-homogeneous scoring functions.
 * In Proceedings of the 21st ACM international conference on Information and 
 * knowledge management (pp. 1065-1074). ACM.
 * http://dl.acm.org/citation.cfm?id=2398404
 * 
 * This software is distributed under the GNU General Public License and as an
 * additional condition of usage, please cite the aforementioned article.
 * 
 * Copyright (C) 2012 ICS/FORTH, Greece and 
 *               2012 LIP6, France
 * 
 * Author: Vouzoukidou Nelly, email: nelly.vouzoukidou (at) gmail (dot) com
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <http://www.gnu.org/licenses/>.
 */
package gr.forth.ics.continuoustopk.index;

import gr.forth.ics.continuoustopk.Item;
import gr.forth.ics.continuoustopk.Constants;
import gr.forth.ics.continuoustopk.Query;
import gr.forth.ics.continuoustopk.Term;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.TreeMap;

/**
 *
 * @author Vouzoukidou Nelly, email: nelly.vouzoukidou (at) gmail (dot) com
 */
public class BucketsQueryIndex extends AbstractQueryIndex {
    private final double[] lowerBounds;

    private final LineStrategy lineStrategy;
    private final double bucketHeight;
    private final double bucketWidth; // only for the no decay strategy
    private final int bucketCapacity;
    private Map<Term, Grid> map;

    BucketsQueryIndex(int lines, int columns, int bucketCapacity, LineStrategy strategy) {
        bucketHeight = 1.0 / lines;
        bucketWidth = 1.0 / columns;
        lowerBounds = tfIdfDistributionBounds(lines);
        this.bucketCapacity = bucketCapacity;
        map = new HashMap<Term, Grid>();
        this.lineStrategy = strategy;
        switch (Constants.decay.type()) {
            case noDecay :
                bucketDivisionStrategy = onNoDecay;
                break;
            case linear :
                bucketDivisionStrategy = onLinearDecay;
                break;
            case exponential :
                bucketDivisionStrategy = onExponentialDecay;
                break;
            default:
                throw new UnsupportedOperationException();
        }
    }

    public void add(Query query) {
        for (int i = 0; i < query.termCount(); i++) {
            Term term = query.getTerm(i);
            Grid grid = map.get(term);
            if (grid == null) {
                grid = new Grid();
                map.put(term, grid);
            }
            grid.add(query, query.getWeight(i));
        }
    }

    @Override
    protected void matchItem(Item item) {
        double max1 = 0;
        Term maxWeightTerm = null;
        double max2 = 0;
        for (int i = 0; i < item.termCount(); i++) {
            double ci = item.getWeight(i);
            if (ci > max1) {
                max2 = max1;
                max1 = ci;
                maxWeightTerm = item.getTerm(i);
            } else if (ci > max2) {
                max2 = ci;
            }
        }

        for (int i = 0; i < item.termCount(); i++) {
            Term term = item.getTerm(i);
            Grid grid = map.get(term);
            if (grid == null) continue;
            double max = term != maxWeightTerm ? max1 : max2;
            grid.match(item, term, item.itemScore(), item.getWeight(i), max);
        }
    }

    @Override
    public Iterable<Query> queries(Term term) {
        Grid grid = map.get(term);
        if (grid == null) {
            return Collections.<Query>emptyList();
        }
        return grid.queries();
    }

    @Override
    public void clear() {
        map.clear();
    }

    public Iterator<Term> terms() {
        return map.keySet().iterator();
    }

    public int queryCount(Term term) {
        Grid grid = map.get(term);
        return grid == null ? 0 : grid.size();
    }

    public static double[] tfIdfDistributionBounds(int buckets) {
        try {
            double[] bounds = new double[buckets];
            Scanner in = new Scanner(new File("props/sortedTfIdf.csv"));
            int totalValues = 397741;
            int mod = (totalValues - 1) / buckets + 1;
            int index = 0;
            for (int lineCount = 0; lineCount < totalValues; lineCount++) {
                String line = in.next();
                if (lineCount % mod == 0) {
                    bounds[index++] = Double.parseDouble(line);
                }
            }
            return bounds;
        } catch (FileNotFoundException e) {
            System.err.println(e.getMessage());
            return null;
        }
    }

    private double scoreBound(double y1, double y2, 
                double cs, double ci, double max, Item item) {
        double LUB = Constants.primaryConstraint.intersection(y1, cs, ci, max);
        LUB = Math.max(LUB, Constants.primaryConstraint.intersection(y2, cs, ci, max));
        double HTA = Constants.secondaryConstraint.intersection(y1, cs, ci, max);
        HTA = Math.max(HTA, Constants.secondaryConstraint.intersection(y2, cs, ci, max));
        return Constants.decay.inverseDecay(Math.min(LUB, HTA), item.timestamp());
    }
    
    class Grid {
        private BucketsLine[] lines;
        private int size;

        Grid() {
            int rows = lowerBounds != null ? lowerBounds.length : (int) (1 / bucketHeight);
            lines = new BucketsLine[rows];
            // don't initialize lines: they are null until at least one is added
        }

        private int getY(double value) {
            if (lowerBounds == null) {
                return Math.min(lines.length - 1, (int) (value / bucketHeight));
            }
            for (int i = 1; i < lowerBounds.length; i++) {
                if (value < lowerBounds[i]) {
                    // it has a lower value than lower bound of the next
                    // line: it belongs to the previous one
                    return i - 1;
                }
            }
            return lowerBounds.length - 1;
        }

        private void add(Query query, double weight) {
            int index = getY(weight);
            BucketsLine bucketsLine = lines[index];
            if (bucketsLine == null) {
                bucketsLine = lineStrategy.getNewLine(BucketsQueryIndex.this);
                lines[index] = bucketsLine;
            }
            bucketsLine.add(query);
            size++;
        }

        private void match(Item item, Term term, double cs, double ci, double max) {
            int visitedBucketCount = 0;
            for (int i = 0; i < lines.length; i++) {
                BucketsLine bucketsLine = lines[i];
                if (bucketsLine == null) continue;
                double y1 = lowerBounds != null ? lowerBounds[i] : i * bucketHeight;
                double y2 = lowerBounds != null ? 
                        (i == lines.length - 1 ? 1 : lowerBounds[i + 1]) : y1 + bucketHeight;

                visitedBucketCount = bucketsLine.match(item, term, y1, y2, cs, ci, max, visitedBucketCount);

            }
        }

        private BucketsLine getLine(int index) {
            return lines[index];
        }

        private int size() {
            return size;
        }

        private Iterable<Query> queries() {
            List<Query> queries = new ArrayList<Query>();
            for (BucketsLine line : lines) {
                if (line != null) {
                    queries.addAll(line.queries());
                }
            }
            return queries;
        }
    }

    abstract class BucketsLine {
        abstract void add(Query query);

        abstract int match(Item item, Term term, double y1, double y2,
                double cs, double ci, double max, int visitedBucketCount);

        abstract Collection<Query> queries();
    }
    
    
    
    // <editor-fold defaultstate="collapsed" desc="Varying Length - Linked List Buckets Line (DensityBuckets)">
    private class VaringWidthListBucketsLine extends BucketsLine {
        private class ZeroWidthBucket extends ListBucket {
            ZeroWidthBucket(double min, ListBucket next, ListBucket previous) {
                super(min, next, previous);
                if (previous == null) {
                    head = this;
                } else if (previous.getClass() == ZeroWidthBucket.class) {
                    ListBucket newPrevious = new ListBucket(previousValue(min), this, previous);
                }
                if (next == null) { // create an extra bucket
                    ListBucket newNext = new ListBucket(nextValue(min), null, this);
                    // next = newNext;
                    tail = next;
                } else if (next.getClass() == ZeroWidthBucket.class) {
                    ListBucket newNext = new ListBucket(nextValue(min), next, this);
                }
            }
            
            @Override
            protected boolean isZero() {
                return true;
            }
            
            @Override
            public boolean add(Query q) {
                return forceAdd(q);
            }
        }

        private class ListBucket extends Bucket {
            private double min;
            protected ListBucket next;
            protected ListBucket previous;

            ListBucket(double min, ListBucket next, ListBucket previous) {
                this.min = min;
                this.next = next;
                this.previous = previous;
                if (previous != null) previous.next = this;
                if (next != null) next.previous = this;
            }

            boolean hasNext() {
                return next != null;
            }

            ListBucket next() {
                return next;
            }

            double min() {
                return min;
            }

            double max() {
                return next == null ? Double.MAX_VALUE : next.min; // TODO: decay
            }

            boolean forceAdd(Query query) {
                return super.add(query);
            }

            @Override
            public boolean add(Query query) {
                if (size() < bucketCapacity) {
                    return super.add(query);
                }
                split(query);
                return true;
            }
            
            double nextValue(double value) {
                 return Double.longBitsToDouble(Double.doubleToLongBits(value) + 1);
            }
            double previousValue(double value) {
                 return Double.longBitsToDouble(Double.doubleToLongBits(value) - 1);
            }
            
            private Query[] sortedQueries(Query query) {
                Query[] queries = new Query[size() + 1];
                super.toArray(queries);
                queries[size()] = query;
                Arrays.sort(queries, minScoreQueryComparator);
                
                return queries;
            }
            
            protected boolean isZero() {
                return false;
            }
            
            ListBucket tryMerge() {
                if (previous == null) {
                    return this;
                }
                if (this.size() + previous.size() > bucketCapacity) {
                    return this;
                }
                
                if (previous.isZero() || (!this.isZero() && this.size() > previous.size())) {
                    // merge in this: copy elements and then delete previous
                    for (int i = 0; i < previous.size(); i++) {
                        this.add(previous.get(i));
                    }
                    if (previous.previous == null) {
                        head = this;
                    } else {
                        previous.previous.next = this;
                    }
                    this.min = previous.min;
                    this.previous = previous.previous;
                    return this;
                }
                // if (this.isZero() || this.size() <= previous.size())
                //     merge in previous
                for (int i = 0; i < this.size(); i++) {
                    previous.add(this.get(i));
                }
                previous.next = this.next;
                if (this.next != null) {
                    this.next.previous = previous;
                } else {
                    tail = previous;
                }
                return previous;
            }
            
            
            ListBucket split(Query query) {
                Query[] queries = sortedQueries(query);
                int indexOfNext = (size() + 1) / 2;
                double midM1 = queries[indexOfNext - 1].minScore();
                // find a different value on the right
                while (indexOfNext < queries.length && midM1 == queries[indexOfNext].minScore()) {
                    indexOfNext++;
                }
                // if it doesn't exist, find a value on the left
                if (indexOfNext > size()) {
                    int indexOfPrevious = (size() + 1) / 2 - 2; // right before the initial indexOfNext
                    while (indexOfPrevious >= 0 && midM1 == queries[indexOfPrevious].minScore()) {
                        indexOfPrevious--;
                    }
                    indexOfNext = indexOfPrevious + 1;
                }
                if (indexOfNext == 0) {
                    // this should be a zero width bucket
                    ZeroWidthBucket newThis = new ZeroWidthBucket(query.minScore(), next, previous);
                    for (int i = 0; i < queries.length; i++) {
                        newThis.add(queries[i]);
                    }
                    // head and tail will be updated in zero width bucket, don't do it here
                    return newThis;
                }
                
                // splitting in the index calculated
                double mid = queries[indexOfNext].minScore();
                ListBucket b = new ListBucket(mid, next, this);
                if (this == tail) {
                    tail = b;
                }
                // add the queries 
                for (int i = size() - 1; i >= 0; i--) {
                    if (get(i).minScore() >= mid) {
                        b.add(get(i));
                        set(i, get(size() - 1));
                        remove(size() - 1);
                    }
                }
                if (query.minScore() >= mid) {
                    b.add(query);
                    return b;
                } else {
                    add(query);
                    return this;
                }
            }
        }
    
        private ListBucket head;
        private ListBucket tail;
        
        private VaringWidthListBucketsLine() {
            head = new ListBucket(0, tail, null);
            tail = head;
        }
        
        private ListBucket get(double value) {
            return get(head, value);
        }
        
        private ListBucket get(ListBucket startFrom, double value) {
            ListBucket prev = null;
            ListBucket curr = startFrom;
            while (curr != null && curr.min <= value) {
                prev = curr;
                curr = curr.next;
            }
            return prev;
        }
        
        private ListBucket getOrCreate(double value) {
            return getOrCreate(head, value);
        }
        
        private ListBucket getOrCreate(ListBucket startFrom, double value) {
            ListBucket b = get(startFrom, value);
            if (b == null) {
                // in case of no decay this never happens
                b = new ListBucket(tail.min + 1, null, tail);
                tail = b;
                return tail.previous;
            }
            return b;
        }
        
        private String lineToString() {
            ListBucket c = head;
            StringBuilder sb = new StringBuilder();
            while (c != null) {
                char ch = c instanceof ZeroWidthBucket ? 'z' : 'l';
                sb.append(c.min).append("(").append(ch).append('-').append(c.size()).append(") ");
                c = c.next;
            }
            return sb.toString();
        }
        
        @Override
        void add(Query query) {
            ListBucket b = getOrCreate(query.minScore());
            b.add(query);
        }
        
        void move(Query query, double s1, double s2) {
            ListBucket from = get(s1);
            ListBucket to = getOrCreate(from, s2);
            if (to == from) {
                return;
            }
            if (!from.remove(query)) {
//                System.err.println(lineToString());
//                System.err.println("Could not find query " + query + "(" + s1 + ") (in bucket " + from.min() + " - " + from.max() + "). ");
            }
            to.add(query);
        }

        @Override
        int match(Item item, Term term, double y1, double y2, 
                double cs, double ci, double max, int visitedBucketCount) {
            double scoreBound = scoreBound(y1, y2, cs, ci, max, item);
            
            // toAdd: contains all queries that will end up to a bucket that does not yet exist
            //        needed to avoid ConcurrentModificationException
            ListBucket bucketFrom = head;
            while (bucketFrom != null) {
                if (bucketFrom.min >= scoreBound) {
                    break;
                }

                Iterator<Query> qIt = bucketFrom.iterator();
                while (qIt.hasNext()) {
                    Query query = qIt.next();
                    double oldScore = query.minScore();
                    double newScore = score(query, item);
                    if (!shouldUpdate(query, newScore)) {
                        notifyVisitedListeners(query, item, term, visitedBucketCount);
                        continue;
                    }
                    // We have to update the score in advance. Otherwise an error occures in the following senario:
                    //   - Query q is inserted in a correct bucket B, WITHOUT the correct minScore
                    //   - For this item B has to be split
                    // ERROR: q does not have the correct value so it will be always on the lower bucket between the two
                    BucketsQueryIndex.this.match(query, item, term, newScore, visitedBucketCount);

                    // query is to be updated:
                    // 1) remove from this bucket and move to new one
                    // 2) update on other positions
                    if (newScore >= bucketFrom.max()) {
                        ListBucket bucketTo = getOrCreate(bucketFrom, newScore);
                        qIt.remove(); // bucketFrom.remove(query);

                        bucketTo.add(query);
                    }
                    for (int i = 0; i < query.termCount(); i++) {
                        if (query.getTerm(i) == term) continue;
                        
                        Grid otherGrid = map.get(query.getTerm(i));
                        VaringWidthListBucketsLine gridLine = (VaringWidthListBucketsLine) otherGrid.getLine(otherGrid.getY(query.getWeight(i)));
                        gridLine.move(query, oldScore, newScore);
                    }
                }
                
                visitedBucketCount++;
                bucketFrom = bucketFrom.tryMerge();
                bucketFrom = bucketFrom.next();
            }
            return visitedBucketCount;
        }

        @Override
        Collection<Query> queries() {
            throw new UnsupportedOperationException("Not supported yet.");
        }
    }

    // </editor-fold>
    
    // <editor-fold defaultstate="collapsed" desc="Varying Length Buckets Line (---)">
    private class BucketWithBounds extends Bucket implements Comparable<BucketWithBounds> {
        private double min;
        private double max;
        
        private BucketWithBounds(double min, double max) {
            super(2);
            this.min = min;
            this.max = max;
        }
        private void setMin(double min) {
            this.min = min;
        }
        
        @Override
        public boolean add(Query q) {
            if (size() >= bucketCapacity) {
                return false;
            }
            return super.add(q);
        }
        
        public void forceAdd(Query q) {
            super.add(q);
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null || obj.getClass() != this.getClass()) {
                return false;
            }
            return this.max == ((BucketWithBounds)obj).max;
        }

        @Override
        public int hashCode() {
            // taken from Double.hashCode()
            long bits = Double.doubleToLongBits(max);
            return (int)(bits ^ (bits >>> 32));
        }

        public int compareTo(BucketWithBounds o) {
            return Double.compare(max, o.max);
        }
        
        public String toString() {
            return super.toString() + " [" + min + "," + max + "]";
        }
    }

    private BucketWithBounds wildcardBucketWithBounds = new BucketWithBounds(0, 1);
    
    private class VaringWidthBucketsLine extends BucketsLine {
        private TreeMap<BucketWithBounds, BucketWithBounds> line;
        private int greatestValue = 0;
        
        private VaringWidthBucketsLine() {
            line = new TreeMap<BucketWithBounds, BucketWithBounds>();
            BucketWithBounds bucket = new BucketWithBounds(0, Long.MIN_VALUE);
            line.put(bucket, bucket);
            bucket = new BucketWithBounds(Long.MIN_VALUE, 1);
            line.put(bucket, bucket);
        }
        
        private BucketWithBounds get(double value) {
            wildcardBucketWithBounds.max = value;
            return line.higherKey(wildcardBucketWithBounds);
        }
        private BucketWithBounds getOrCreate(double value) {
            BucketWithBounds b = get(value);
            if (b == null) {
                // in case of no decay this never happens
                b = new BucketWithBounds(greatestValue, greatestValue + 1);
                greatestValue++;
                line.put(b, b);
            }
            return b;
        }
        
        @Override
        void add(Query query) {
            BucketWithBounds b = getOrCreate(query.minScore());
            addInBucket(query, b);
        }
        
        private BucketWithBounds addInBucket(Query query, BucketWithBounds b) {
            if (b.add(query)) {
                // if the capacity is ok, add it
                return b;
            }
            if (query.minScore() == 0) {
                b.forceAdd(query);
                return b;
            }
            
            // making sure that at least one value will be included in the other bucket
            double midValue = Math.max(query.minScore(), b.get(0).minScore());
            for (int i = 1; i < b.size() && 
                    (midValue == b.min); i++) {
                midValue = b.get(i).minScore(); // always >= to b.min
            }
            if (midValue == b.min) {
                b.forceAdd(query);
                return b;
            }
            BucketWithBounds b0 = new BucketWithBounds(b.min, midValue);
            b.setMin(midValue);
            line.put(b0, b0);
            
            for (int i = b.size() - 1; i >= 0; i--) {
                Query q = b.get(i);
                if (q.minScore() < midValue) {
                    // "delete" it
                    b0.add(q);
                    b.set(i, b.get(b.size() - 1));
                    b.remove(b.size() - 1);
                }
            }
            if (query.minScore() < midValue) {
                b0.add(query);
                return b0;
            }
            b.add(query);
            return b;
        }
        
        void move(Query query, double s1, double s2) {
            BucketWithBounds from = get(s1);
            BucketWithBounds to = getOrCreate(s2);
            if (to == from) {
                return;
            }
            if (!from.remove(query)) {
                throw new IllegalStateException("Could not find query " + query + "(" + s1 + ") (in bucket " + from.min + " - " + from.max + "). ");
            }
            to = addInBucket(query, to);
        }

        @Override
        int match(Item item, Term term, double y1, double y2, 
                double cs, double ci, double max, int visitedBucketCount) {
            double scoreBound = scoreBound(y1, y2, cs, ci, max, item);
            
            // toAdd: contains all queries that will end up to a bucket that does not yet exist
            //        needed to avoid ConcurrentModificationException
            List<Query> toAdd = new ArrayList<Query>();
            Iterator<Entry<BucketWithBounds, BucketWithBounds>> it = line.entrySet().iterator();
            while (it.hasNext()) {
                BucketWithBounds bucketFrom = it.next().getKey();
                if (bucketFrom.min > scoreBound) {
                    break;
                }
                
                Iterator<Query> qIt = bucketFrom.iterator();
                while (qIt.hasNext()) {
                    Query query = qIt.next();
                    double oldScore = query.minScore();
                    double newScore = score(query, item);
                    if (!shouldUpdate(query, newScore)) {
                        notifyVisitedListeners(query, item, term, visitedBucketCount);
                        continue;
                    }
                    // We have to update the score in advance. Otherwise an error occures in the following senario:
                    //   - Query q is inserted in a correct bucket B, WITHOUT the correct minScore
                    //   - For this item b has to be split
                    // ERROR: q does not have the correct value so it will be always on the lower bucket between the two
                    BucketsQueryIndex.this.match(query, item, term, newScore, visitedBucketCount);

                    // query is to be updated:
                    // 1) remove from this bucket and move to new one
                    // 2) update on other positions
                    if (newScore >= bucketFrom.max) {
                        BucketWithBounds bucketTo = getOrCreate(newScore);
                        qIt.remove(); // bucketFrom.remove(query);

                        if (!bucketTo.add(query)) {
                            // cannot add now: it will split the old bucket and cause a concurrent modification error
                            toAdd.add(query);
                        }
                    }
                    for (int i = 0; i < query.termCount(); i++) {
                        if (query.getTerm(i) == term) continue;
                        
                        Grid otherGrid = map.get(query.getTerm(i));
                        VaringWidthBucketsLine gridLine = (VaringWidthBucketsLine) otherGrid.getLine(otherGrid.getY(query.getWeight(i)));
                        gridLine.move(query, oldScore, newScore);
                    }
                }
//                if (bucketFrom.isEmpty()) {
//                    it.remove(); // line.remove(bucketFrom);
//                }
                visitedBucketCount++;
            }
            for (Query query : toAdd) {
                add(query);
            }
            return visitedBucketCount;
        }

        @Override
        Collection<Query> queries() {
            throw new UnsupportedOperationException("Not supported yet.");
        }
        
    }
    // </editor-fold>
    
    // <editor-fold defaultstate="collapsed" desc="Sorted Buckets Line (SortedBuckets)">
    private class BucketWithIndex extends Bucket implements Comparable<BucketWithIndex> {
        private int index;
        
        BucketWithIndex(int index) {
            this.index = index;
        }
        
        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (obj.getClass() != this.getClass()) {
                return false;
            }
            return this.index == ((BucketWithIndex)obj).index;
        }

        @Override
        public int hashCode() {
            return index;
        }

        public int compareTo(BucketWithIndex b) {
            return index - b.index;
        }
        
    }
    
    private BucketWithIndex wildcardBucketWithIndex = new BucketWithIndex(0);
    private BucketDivision bucketDivisionStrategy;
    
    private class SortedBucketsLine extends BucketsLine {
        private Map<BucketWithIndex, BucketWithIndex> line = new TreeMap<BucketWithIndex, BucketWithIndex>();
        
        private int getX(double minScore) {
            return bucketDivisionStrategy.indexForScore(minScore);
        }
        
        private BucketWithIndex get(int index) {
            wildcardBucketWithIndex.index = index;
            return line.get(wildcardBucketWithIndex);
        }
        
        private BucketWithIndex getOrCreate(int index) {
            BucketWithIndex bucket = get(index);
            if (bucket == null) {
                bucket = new BucketWithIndex(index);
                line.put(bucket, bucket);
            }
            return bucket;
        }
        
        private void move(Query query, int indexFrom, int indexTo) {
            BucketWithIndex from = get(indexFrom);
            BucketWithIndex to = get(indexTo);
            if (from.size() == 1) {
                line.remove(from);
                if (to == null) {
                    from.index = indexTo;
                    line.put(from, from);
                } else {
                    to.add(query);
                    //from will be garbage collected
                }
                return;
            }
            from.remove(query);
            if (to == null) {
                to = new BucketWithIndex(indexTo);
                line.put(to, to);
            }
            to.add(query);
        }
        
        @Override
        void add(Query query) {
            getOrCreate(getX(query.minScore())).add(query);
        }

        @Override
        int match(Item item, Term term, double y1, double y2, double cs, double ci, double max, int visitedBucketCount) {
            double scoreBound = scoreBound(y1, y2, cs, ci, max, item);
            int endIndex = getX(scoreBound);
            // toAdd: contains all queries that will end up to a bucket that does not yet exist
            //        needed to avoid ConcurrentModificationException
            List<Query> toAdd = new ArrayList<Query>();
            Iterator<Entry<BucketWithIndex, BucketWithIndex>> it = line.entrySet().iterator();
            while (it.hasNext()) {
                BucketWithIndex bucketFrom = it.next().getKey();
                if (bucketFrom.index > endIndex) {
                    break;
                }
                
                Iterator<Query> qIt = bucketFrom.iterator();
                while (qIt.hasNext()) {
                    Query query = qIt.next();
                    double score = score(query, item);
                    if (!shouldUpdate(query, score)) {
                        notifyVisitedListeners(query, item, term, visitedBucketCount);
                        continue;
                    }
                    // query is to be updated:
                    // 1) remove from this bucket and move to new one
                    // 2) update on other positions
                    int indexFrom = bucketFrom.index;
                    int indexTo = getX(score);
                    
                    if (indexFrom == indexTo) { // early exit: nothing to move
                        BucketsQueryIndex.this.match(query, item, term, score, visitedBucketCount);
                        continue;
                    }
                    qIt.remove(); // bucketFrom.remove(query);
                    BucketWithIndex bucketTo = get(indexTo);
                    if (bucketTo == null) {
                        toAdd.add(query);
                    } else {
                        bucketTo.add(query);
                    }
                    for (int i = 0; i < query.termCount(); i++) {
                        if (query.getTerm(i) == term) continue;
                        
                        Grid otherGrid = map.get(query.getTerm(i));
                        SortedBucketsLine gridLine = (SortedBucketsLine) otherGrid.getLine(otherGrid.getY(query.getWeight(i)));
                        gridLine.move(query, indexFrom, indexTo);
                    }
                    BucketsQueryIndex.this.match(query, item, term, score, visitedBucketCount);
                }
                if (bucketFrom.isEmpty()) {
                    it.remove(); // line.remove(bucketFrom);
                }
            }
            for (Query query : toAdd) {
                add(query);
            }
            return visitedBucketCount + 1;
        }

        @Override
        Collection<Query> queries() {
            Collection<Query> queries = new ArrayList<Query>();
            for (BucketWithIndex bucket : line.keySet()) {
                queries.addAll(bucket);
            }
            return queries;
        }
    }
    // <editor-fold defaultstate="collapsed" desc="BucketsLine strategies">
    private static double minAccuracy = 1.12667E-06;
    private double sigma = Math.log(minAccuracy) * BucketsQueryIndex.this.bucketWidth;
    
    private BucketDivision onNoDecay = new BucketDivision() {
        double valueForBucket(int index) {
            return index * bucketWidth;
        }
        int indexForScore(double score) {
            return Math.min((int) (score / bucketWidth), (int) (1 / bucketWidth) - 1);
        }
    };
    private BucketDivision onLinearDecay = new BucketDivision() {
        double valueForBucket(int index) {
            return index * bucketWidth;
        }
        int indexForScore(double score) {
            return (int) (score / bucketWidth);
        }
    };
    private BucketDivision onExponentialDecay = new BucketDivision() {
        double valueForBucket(int index) {
            return Math.pow(sigma, index);
        }
        int indexForScore(double score) {
            return (int) (Math.log(score) / Math.log(sigma));
        }
    };
        
    private abstract static class BucketDivision {
        
        abstract double valueForBucket(int index);
        abstract int indexForScore(double score);
    }
    // </editor-fold>
    
    
    //</editor-fold>

    // <editor-fold defaultstate="collapsed" desc="Sorted by min score line (SortedQueries)">
    private static Comparator<Query> minScoreQueryComparator = new Comparator<Query>() {
        public int compare(Query q1, Query q2) {
            if (q1 == q2) {
                return 0;
            }
            double min1 = q1.minScore();
            double min2 = q2.minScore();

            if (min1 < min2) {
                return -1;
            } else if (min1 > min2) {
                return 1;
            }
            // equal minscores: giving some random ordering (otherwise the two
            // queries would be considered equal by the treemap and one of
            // them would be ignored)
            if (q1.hashCode() == q2.hashCode()) {
                if (!q1.equals(q2)) {
//                    System.err.println("ERROR in hashCode of queries (" + q1.hashCode() + ")" + q1 + ", " + q2);
                    return q1.toString().compareTo(q2.toString());
                }
            }
            return q1.hashCode() > q2.hashCode() ? 1 : -1;
        }
    };
    private class SortedQueriesLine extends BucketsLine {
        private TreeMap<Query, Query> line;
        
        SortedQueriesLine() {
            line = new TreeMap<Query, Query>(minScoreQueryComparator);
        }
        
        @Override
        void add(Query query) {
            line.put(query, query);
        }
        
        private void move(Query query, double oldScore, double newScore) {
            line.remove(query);
            query.setMinScore(newScore);
            line.put(query, query);
            query.setMinScore(oldScore);
        }

        @Override
        int match(Item item, Term term, double y1, double y2, double cs, double ci, double max, int visitedBucketCount) {           
            double scoreBound = scoreBound(y1, y2, cs, ci, max, item);

            List<Query> toAdd = new ArrayList<Query>();
            Iterator<Query> it = line.keySet().iterator();
            
            //iterator/delete/ add all at the end/ don't forget the other terms of the query
            while (it.hasNext()) {
                Query query = it.next();
                double oldScore = query.minScore();
                if (oldScore > scoreBound) {
                    notifyVisitedListeners(query, item, term, visitedBucketCount);
                    break;
                }
                double score = score(query, item);
                if (!shouldUpdate(query, score)) {
                    notifyVisitedListeners(query, item, term, visitedBucketCount);
                    continue;
                }

                if (updateStrategy == UpdateStrategy.update) {
                    // remove it first
                    it.remove();
                    toAdd.add(query);

                    // it has to be moved here: later we won't know its old score
                    for (int i = 0; i < query.termCount(); i++) {
                        if (query.getTerm(i) == term) {
                            continue;
                        }
                        Grid otherGrid = map.get(query.getTerm(i));
                        SortedQueriesLine gridLine = (SortedQueriesLine) otherGrid.getLine(otherGrid.getY(query.getWeight(i)));
                        gridLine.move(query, oldScore, score);
                    }
                }
                BucketsQueryIndex.this.match(query, item, term, score, visitedBucketCount);
            }
            for (Query query : toAdd) {
                line.put(query, query);
            }
            return visitedBucketCount + 1;
        }

        @Override
        Collection<Query> queries() {
            return line.keySet();
        }
        
    }
    //</editor-fold>

    // <editor-fold defaultstate="collapsed" desc="Static Array Line (Grid2D)">
    private class StaticArrayLine extends BucketsLine {
        private Bucket[] buckets;
        private StaticArrayLine() {
            int columns = (int) (1 / bucketWidth);
            buckets = new Bucket[columns];
        }
        
        int getX(double value) {
            return Math.min(buckets.length, (int) (value / bucketWidth));
        }

        @Override
        void add(Query query) {
            // add it based on its minimum score
            add(query, getX(query.minScore()));
        }

        void add(Query query, int bucket) {
            Bucket b = buckets[bucket];
            if (b == null) {
                b = new Bucket();
                buckets[bucket] = b;
            }
            b.add(query);
        }

        void remove(Query query, int bucket) {
            Bucket b = buckets[bucket];
            if (b.size() == 1) {
                buckets[bucket] = null;
            } else {
                b.remove(query);
            }
        }
        
        void move(Query query, int from, int to) {
            if (buckets[from].size() == 1 && buckets[to] == null) {
                buckets[to] = buckets[from];
                buckets[from] = null;
                return;
            }
            buckets[from].remove(query);
            if (buckets[to] == null) {
                buckets[to] = new Bucket();
            }
            buckets[to].add(query);
        }

        @Override
        int match(Item item, Term term, double y1, double y2,
                double cs, double ci, double max, int visitedBucketCount) {
            double scoreBound = scoreBound(y1, y2, cs, ci, max, item);
            int rightmostBucket = getX(scoreBound);

            for (int j = rightmostBucket; j >= 0; j--) {
                Bucket bucket = buckets[j];
                // visit all elements of the bucket
                if (bucket != null) {
                    updateBucket(bucket, term, item, visitedBucketCount);
                }
                visitedBucketCount++;
            }
            return visitedBucketCount;
        }

        private void updateBucket(Bucket bucket, Term term, Item item,
                int visitedBucketCount) {
            Iterator<Query> queries = bucket.iterator();
            while (queries.hasNext()) {
                Query query = queries.next();
                double score = score(query, item);
                if (shouldUpdate(query, score)) {
                    double oldScore = query.minScore();
                    BucketsQueryIndex.this.match(query, item, term, score, visitedBucketCount);
                    // TODO: add it somehow in the UpdateStrategy enum
                    if (updateStrategy == UpdateStrategy.update) {
                        int newBucket = getX(score);
                        int oldBucket = getX(oldScore);
                        if (oldBucket != newBucket) {
                            queries.remove();
                            Bucket b = buckets[newBucket];
                            if (b == null) {
                                b = new Bucket();
                                buckets[newBucket] = b;
                            }
                            b.add(query);
                            for (int j = 0; j < query.termCount(); j++) {
                                if (query.getTerm(j) == term) {
                                    continue;
                                }
                                Grid otherGrid = map.get(query.getTerm(j));
                                double value = query.getWeight(j);
                                int y = otherGrid.getY(value); //(int) (value / bucketHeight);
//                                if (value == 1) y--;
                                StaticArrayLine line = ((StaticArrayLine) otherGrid.getLine(y));
                                line.move(query, oldBucket, newBucket);
                            }
                        }
                    }
                } else {
                    notifyVisitedListeners(query, item, term, visitedBucketCount);
                }
            }
        }

        @Override
        Collection<Query> queries() {
            List<Query> queries = new ArrayList<Query>();
            for (Bucket bucket : buckets) {
                if (bucket != null) {
                    queries.addAll(bucket);
                }
            }
            return queries;
        }
    }
    // </editor-fold>
    
    private BucketsLine newStaticArrayLine() {
        return new StaticArrayLine();
    }
    private BucketsLine newSortedBucketsLine() {
        return new SortedBucketsLine();
    }
    private BucketsLine newSortedQueriesLine() {
        return new SortedQueriesLine();
    }
    private BucketsLine newVaringWidthListBucketsLine() {
        return new VaringWidthListBucketsLine();
    }
    
    public enum LineStrategy {
        rectangularGrid {
            @Override
            public BucketsLine getNewLine(BucketsQueryIndex index) {
                return index.newStaticArrayLine();
            }
        },
        sortedBuckets {
            @Override
            public BucketsLine getNewLine(BucketsQueryIndex index) {
                return index.newSortedBucketsLine();
            }
        },
        sortedQueries {
            @Override
            public BucketsLine getNewLine(BucketsQueryIndex index) {
                return index.newSortedQueriesLine();
            }
        },
        densityBuckets {
            @Override
            public BucketsLine getNewLine(BucketsQueryIndex index) {
                return index.newVaringWidthListBucketsLine();
            }
        };
        
        abstract BucketsLine getNewLine(BucketsQueryIndex index);
    }
    
    class Bucket extends ArrayList<Query> {
        private Bucket() {}
        
        private Bucket(int capacity) {
            super(capacity);
        }
    }
}
